package com.mj;

import com.mj.printer.BinaryTreeInfo;
import com.sun.org.apache.bcel.internal.generic.NOP;
import sun.reflect.generics.visitor.Visitor;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * E extends Comparable
 * E 这个类必须遵守Comparable 实现接口
 * <p>
 * 二叉搜索树必须拥有可比较的特点
 *
 * @param <E>
 */
public class BinarySearchTree<E> implements BinaryTreeInfo {

    private int size;
    private Node<E> root;//根节点
    private Comparator<E> comparator;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    //打印什么
    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentString + ")";
    }

    private static class Node<E> {
        Node<E> parent;//常用到
        Node<E> left;
        Node<E> right;
        E element;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }
    }

    /**
     * @param element1
     * @param element2
     * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
     */
    private int compare(E element1, E element2) {
        if (comparator != null)
            return comparator.compare(element1, element2);
        //强制转换为Comparable接口的实现类
        return ((Comparable<E>) element1).compareTo(element2);

    }

    // 元素的数量**
    public int size() {
        return size;
    }

    // 是否为空**
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空所有元素
    public void clear() {
        size = 0;
        root = null;

    }
    //接口只允许定义方法

    public static abstract class Visitor<E> {
        boolean stop;
        /**
         * @param element
         * @return 如果返回true，就代表停止遍历
         */
        abstract boolean visit(E element);
    }


    /**
     * 前序遍历
     */
    public void preorder(Visitor<E> visitor) {
        if (visitor == null) return;
        preorder(root, visitor);
    }

    private void preorder(Node<E> node, Visitor<E> visitor) {
        //停止递归和打印
        if (node == null || visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        preorder(node.left, visitor);
        preorder(node.right, visitor);
    }

    /**
     * 中序遍历
     */
    public void inorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        inorderTraversal(root, visitor);
    }

    private void inorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;

        inorderTraversal(node.left, visitor);
        //停止打印
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorderTraversal(node.right, visitor);

//        倒着中序遍历
//        inorderTraversal(node.right);
//        System.out.println(node.element);
//        inorderTraversal(node.left);

    }

    /**
     * 后序遍历
     */
    public void postorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        postorderTraversal(visitor, root);
    }

    private void postorderTraversal(Visitor<E> visitor, Node<E> node) {
        //停止递归
        if (node == null || visitor.stop) return;

        postorderTraversal(visitor, node.left);
        postorderTraversal(visitor, node.right);
        //停止打印
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }

    /**
     * 层序遍历
     */
    public void levelTraversal(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            //节点对外不可见
            if (visitor.visit(node.element)) return;
//            System.out.println(node.element);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }


    // 添加元素
    public void add(E element) {
        elementNotNullCheck(element);
        //第一种情况 根节点为空时
        if (root == null) {
            //根节点没有头节点
            root = new Node<>(element, null);
            size++;
            return;
        }
        //往根节点添加元素
        Node<E> node = root;
        Node<E> parent = root;
        int compare = 0;
        while (node != null) {
            compare = compare(element, node.element);
            //在移动之前 先把父节点保存起来
            parent = node;
            if (compare > 0) {
                node = node.right;
            } else if (compare < 0) {
                node = node.left;
            } else {
                //覆盖
                node.element = element;
                return;
            }
        }
        Node<E> newNode = new Node<>(element, parent);
        if (compare > 0) parent.right = newNode;
        else parent.left = newNode;

        size++;
    }


    // 删除元素**
    public void remove(E element) {
        remove(node(element));
    }

    private void remove(Node<E> node) {
        if (node == null) return;

        //特殊处理度为2的节点，做到删除度为1或度为0的节点时代码复用
        if (node.hasTwoChildren()) { //度为2的节点
            //找到后继节点
//            Node<E> predecessor = predecessor(node);
            Node<E> s = successor(node);
            //用后继节点的值覆盖度为2的节点的值
            node.element = s.element;
            //将node指向后继节点，然后删除node节点（successor）
            node = s;
        }
        //删除node节点（node的度必然是 1或0）
        Node<E> replacement = node.left != null ? node.left : node.right;
        //node的度必然是 1
        if (!node.isLeaf()) replacement.parent = node.parent;          //修改父节点

        //更改parent的left. right的指向
        if (node.parent == null) root = replacement;//node是度为1的节点并且是根节点
        else if (node == node.parent.right) node.parent.right = replacement;
        else if (node == node.parent.left) node.parent.left = replacement;
        size--;
//        if (node.isLeaf()) {
//            if (node.parent == null) root = null;
//            else if (node == node.parent.right) node.parent.right = null;
//            else if (node == node.parent.left) node.parent.left = null;
//
//        }else {
//            Node<E> replacement =  node.left !=null ? node.left :node.right;
//            //修改父节点
//            replacement.parent = node.parent;
//            //更改parent的left. right的指向
//            if (node.parent == null) root = replacement;//node是度为1的节点并且是根节点
//            else if (node == node.parent.right)  node.parent.right = replacement;
//            else if (node == node.parent.left)  node.parent.left = replacement;
//        }
//        size--;
    }

    /**
     * 通过元素获取节点
     *
     * @param element
     * @return
     */
    private Node<E> node(E element) {
        Node<E> node = this.root;
        while (node != null) {
            int com = compare(element, node.element);
            if (com == 0) return node;
            if (com > 0) node = node.right;
            else node = node.left;// com < 0
        }
        return null;
    }

    // 是否包含某元素
    public boolean contains(E element) {
        return node(element) != null;
    }


    /**
     * 迭代 用层序遍历计算高度
     * 每一层的元素数量是当前队列的长度
     * 元素弹出，队列长度-1
     * 当每一层的所有元素弹出(队列长度等于0)时，这一层就访问完了，height++
     *
     * @return
     */
    public int height() {
        if (root == null) return 0;
        int height = 0;
        //存储着每一层的元素数量
        int levelSize = 1;

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            if (levelSize == 0) {//意味着即将访问下一层
                height++;
                levelSize = queue.size();
            }
        }
        return height;
    }

    /**
     * 递归
     * 每个节点的高度等于 子节点中最大的高度+1
     */
    public int height2() {
        return height2(root);
    }

    private int height2(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height2(node.left), height2(node.right));
    }

    /**
     * 判断一棵树是否为完全二叉树(逻辑清晰版)
     *
     * @return
     */
    public boolean isComplete() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {// node.left == null && node.right != null
                return false;
            }
            if (node.right != null) {
                queue.offer(node.right);
            } else { // node.right = null
                leaf = true;
            }
        }
        return true;
    }

    /**
     * 判断一棵树是否为完全二叉树
     *
     * @return
     */
    public boolean isComplete1() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;
            if (node.hasTwoChildren()) {
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right != null) {
                return false;
            } else {//后面遍历的节点都必须是叶子节点
                leaf = true;
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }
        }
        return true;
    }

    /**
     * 前驱节点
     *
     * @return
     */
    public Node<E> predecessor(Node<E> node) {
        if (node == null) return null;

        //前驱节点在左子树当中（left.right.right.right. . . .)
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        // 从父节点、祖父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }
        // node.parent = null
        // node == node.parent.right
        return node.parent;
    }

    /**
     * 后驱节点
     *
     * @return
     */
    public Node<E> successor(Node<E> node) {
        if (node == null) return null;

        //前驱节点在右子树当中（right.left.left.left. . . .)
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        // 从父节点、祖父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }
        // node.parent = null
        // node == node.parent.left
        return node.parent;
    }


    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        toString(root, builder, "");
        return builder.toString();
    }

    private void toString(Node<E> node, StringBuilder builder, String prefix) {
        if (node == null) return;
        builder.append(prefix).append(node.element).append("\n");
        toString(node.left, builder, prefix + "L---");
        toString(node.right, builder, prefix + "R---");
    }

    /**
     * 检查元素是否为空
     */
    private void elementNotNullCheck(E element) {
        if (element == null)
            throw new IllegalArgumentException("element must not be null");
    }
}
